package leetcode;

/**
 * 333.最大 BST 子树    https://leetcode.com/problems/largest-bst-subtree
 * 待验证
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2023-05-19
 */
public class LeetCode333 {

    // 提交时不要提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            val = value;
        }
    }

    // 提交如下的代码，可以直接通过
    public static class Info {
        public int maxBSTSubSize;
        public int size;
        public int min;
        public int max;

        public Info(int m, int s, int mi, int ma) {
            this.maxBSTSubSize = m;
            this.size = s;
            this.min = mi;
            this.max = ma;
        }
    }

    public static int largestBSTSubtree(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return process(head).maxBSTSubSize;
    }

    public static Info process(TreeNode head) {
        if (head == null) {
            return null;
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int maxBSTSubSize = 0;
        int size = 1;
        int min = head.val;
        int max = head.val;
        if (leftInfo != null) {
            maxBSTSubSize = leftInfo.maxBSTSubSize;
            size += leftInfo.size;
            min = Math.min(min, leftInfo.min);
            max = Math.max(max, leftInfo.max);
        }
        if (rightInfo != null) {
            maxBSTSubSize = rightInfo.maxBSTSubSize;
            size += rightInfo.size;
            min = Math.min(min, rightInfo.min);
            max = Math.max(max, rightInfo.max);
        }
        boolean isLeftBST = leftInfo == null || (leftInfo.maxBSTSubSize == leftInfo.size);
        boolean isRightBST = rightInfo == null || (rightInfo.maxBSTSubSize == rightInfo.size);
        if (isLeftBST && isRightBST) {
            boolean leftMaxLessX = leftInfo == null || (leftInfo.max < head.val);
            boolean rightMinMoreX = rightInfo == null || (head.val > rightInfo.min);
            // 当前节点值大于左子树最大值，小于右子树最大值
            if(leftMaxLessX && rightMinMoreX){
                int leftBSTSize = leftInfo == null ? 0 : leftInfo.maxBSTSubSize;
                int rightBSTSize = rightInfo == null ? 0 : rightInfo.maxBSTSubSize;
                maxBSTSubSize = Math.max(maxBSTSubSize, leftBSTSize + rightBSTSize + 1);
            }
        }
        return new Info(maxBSTSubSize, size, min, max);
    }
}
